/**
 * https://leetcode-cn.com/problems/2-keys-keyboard/
 * 
 * 给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。
 * @param n 
 */
const minSteps = (n: number): number => {
    // 输入A的数量小于等于1, 直接返回0
    if (n <= 1) return 0;

    // dp[i]表示打印出i个A的最少操作数
    const dp = new Array(n + 1).fill(0);

    // i表示打印出i个A的最少操作数量
    for (let i = 2; i <= n; i++) {
        // 将该项置为最大
        dp[i] = Infinity;

        // j表示赋值的次数
        for (let j = 1; j * j <= i; j++) { // j * j表示复制出来一共的数量
            // 能整除
            if (i % j === 0) {
                // 1. dp[j] 加上全部使用p
                // 复制一次, 全部使用粘贴
                dp[i] = Math.min(dp[i], dp[j] + i / j);

                // 2. 使用c + p
                dp[i] = Math.min(dp[i], dp[i / j] + j);
            }
        }

    }
    return dp[n]
};

console.log(minSteps(4))

/**
 * 满足可以执行的操作, 但是不是最少的操作
 * @param n 
 */
const minSteps2 = (n: number): number => {
    // 输入A的数量小于等于1, 直接返回0
    if (n <= 1) return 0;

    let aCount = 1, // a的数量
        count = 0; // 操作数的数量

    // 是否进行了c操作
    let state = false,
        cCount = 1; // c操作拷贝的数量
    const arr = []
    // 直到aCount等于n, 才结束 
    while (aCount < n) {
        // 满足a的数量 × 2 <= n, 尝试进行c操作
        if ((aCount << 1) <= n) {
            // 进行c操作后, 剩余的数量要大于之前这次要拷贝的数量
            // state === false 表示默认第一次就是要c操作
            if (!state || (((n - (aCount << 1)) & 1) !== 1) && (n - (aCount << 1)) >= aCount) {
                // c操作, 操作数 + 1
                arr.push('c');
                count++;
                state = true; // 标记为已经c操作
                cCount = aCount; // c操作的数量为a的数量

                // a的数量翻倍 (进行p操作)
                aCount = (aCount << 1);
            } else {
                // 不满足这次的c操作, 进行p操作

                // a的数量 加上之前的c的数量
                aCount += cCount;
            }
        } else {
            // 不满足尝试的c操作, 进行p操作
            aCount += cCount;
        }
        // 操作数加1 (p操作)
        arr.push('p')
        count++;

        // p操作后恰好等于要打印的A数量
        if (aCount === n) {
            console.log(arr);
            return count;
        }
    }

    console.log(arr);
    return count;
};


// const n = minSteps(3)
// console.log(n);